package com.lw.leetcode.arr.c;

/**
 * Created with IntelliJ IDEA.
 * arr
 * 330. 按要求补齐数组
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/2 13:28
 */
public class MinPatches {


    public static void main(String[] args) {
        MinPatches test = new MinPatches();

        // 1
//        int[] arr = {1, 3};
//        int n = 6;

        // 2
//        int[] arr = {1, 5, 10};
//        int n = 20;

        // 0
//        int[] arr = {1, 2, 2};
//        int n = 5;

        // 1
        int[] arr = {1, 2, 2, 6, 34, 38, 41, 44, 47, 47, 56, 59, 62, 73, 77, 83, 87, 89, 94};
        int n = 20;

//        int[] arr = Utils.getArr(10, 0, 100, true);
//        int n = Integer.MAX_VALUE;
//        int n = 1000;
//        System.out.println(n);


        int i = test.minPatches(arr, n);
        System.out.println(i);
    }

    public int minPatches(int[] nums, int n) {
        int count = 0;
        long sum = 0;
        for (int num : nums) {
            if (sum >= n) {
                return count;
            }
            if (num == sum + 1) {
                sum += num;
                continue;
            }
            while (sum < num - 1 && sum < n) {
                sum += (sum + 1);
                count++;
            }
            sum += num;
        }
        while (sum < n) {
            sum += (sum + 1);
            count++;
        }
        return count;
    }

    public int minPatches2(int[] nums, int n) {
        //此处用int会溢出
        long ach = 0;
        int idx = 0, count = 0, len = nums.length;
        while (ach < n) {
            if (idx >= len || ach + 1 < nums[idx]) {
                count++;
                ach += ach + 1;
            } else {
                ach += nums[idx];
                idx++;
            }
        }
        return count;
    }

}
